home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / ptpoly_haines / ptinpoly.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  6.3 KB  |  215 lines
  1. /* ptinpoly.h - point in polygon inside/outside algorithms header file.
  2.  *
  3.  * by Eric Haines, 3D/Eye Inc, erich@eye.com
  4.  */
  5.  
  6. /* Define CONVEX to compile for testing only convex polygons (when possible,
  7.  * this is faster) */
  8. /* #define CONVEX */
  9.  
  10. /* Define HYBRID to compile triangle fan test for CONVEX with exterior edges
  11.  * meaning an early exit (faster - recommended).
  12.  */
  13. /* #define HYBRID */
  14.  
  15. /* Define DISPLAY to display test triangle and test points on screen */
  16. /* #define DISPLAY */
  17.  
  18. /* Define RANDOM to randomize order of edges for exterior test (faster -
  19.  * recommended). */
  20. /* #define RANDOM */
  21.  
  22. /* Define SORT to sort triangle edges and areas for half-plane and Spackman
  23.  * tests (faster - recommended).
  24.  * The bad news with SORT for non-convex testing is that this usually messes
  25.  * up any coherence for the triangle fan tests, meaning that points on an
  26.  * interior edge can be mis-classified (very rare, except when -c is used).
  27.  * In other words, if a point lands on an edge between two test triangles,
  28.  * normally it will be inside only one - sorting messes up the test order and
  29.  * makes it so that the point can be inside two.
  30.  */
  31. /* #define SORT */
  32.  
  33. /* Define WINDING if a non-zero winding number should be used as the criterion
  34.  * for being inside the polygon.  Only used by the general crossings test and
  35.  * Weiler test.     The winding number computed for each is the number of
  36.  * counter-clockwise loops the polygon makes around the point.
  37.  */
  38. /* #define WINDING */
  39.  
  40. /* =========================== System Related ============================= */
  41.  
  42. /* define your own random number generator, change as needed */
  43. /* SRAN initializes random number generator, if needed */
  44. #define SRAN()        srand48(1)
  45. /* RAN01 returns a double from [0..1) */
  46. #define RAN01()        drand48()
  47. double    drand48() ;
  48.  
  49. /* On systems without drand48() you might do this instead (though check if
  50.  * rand()'s divisor is correct for your machine):
  51. #define SRAN()        srand(1)
  52. #define RAN01()        ((double)rand() / 32768.0)
  53. */
  54.  
  55. /* =========== Grid stuff ================================================= */
  56.  
  57. #define GR_FULL_VERT    0x01    /* line crosses vertically */
  58. #define GR_FULL_HORZ    0x02    /* line crosses horizontally */
  59.  
  60. typedef struct {
  61.     double    xa,ya ;
  62.     double    minx, maxx, miny, maxy ;
  63.     double    ax, ay ;
  64.     double    slope, inv_slope ;
  65. } GridRec, *pGridRec;
  66.  
  67. #define GC_BL_IN    0x0001    /* bottom left corner is in (else out) */
  68. #define GC_BR_IN    0x0002    /* bottom right corner is in (else out) */
  69. #define GC_TL_IN    0x0004    /* top left corner is in (else out) */
  70. #define GC_TR_IN    0x0008    /* top right corner is in (else out) */
  71. #define GC_L_EDGE_HIT    0x0010    /* left edge is crossed */
  72. #define GC_R_EDGE_HIT    0x0020    /* right edge is crossed */
  73. #define GC_B_EDGE_HIT    0x0040    /* bottom edge is crossed */
  74. #define GC_T_EDGE_HIT    0x0080    /* top edge is crossed */
  75. #define GC_B_EDGE_PARITY    0x0100    /* bottom edge parity */
  76. #define GC_T_EDGE_PARITY    0x0200    /* top edge parity */
  77. #define GC_AIM_L    (0<<10) /* aim towards left edge */
  78. #define GC_AIM_B    (1<<10) /* aim towards bottom edge */
  79. #define GC_AIM_R    (2<<10) /* aim towards right edge */
  80. #define GC_AIM_T    (3<<10) /* aim towards top edge */
  81. #define GC_AIM_C    (4<<10) /* aim towards a corner */
  82. #define GC_AIM        0x1c00
  83.  
  84. #define GC_L_EDGE_CLEAR GC_L_EDGE_HIT
  85. #define GC_R_EDGE_CLEAR GC_R_EDGE_HIT
  86. #define GC_B_EDGE_CLEAR GC_B_EDGE_HIT
  87. #define GC_T_EDGE_CLEAR GC_T_EDGE_HIT
  88.  
  89. #define GC_ALL_EDGE_CLEAR    (GC_L_EDGE_HIT | \
  90.                  GC_R_EDGE_HIT | \
  91.                  GC_B_EDGE_HIT | \
  92.                  GC_T_EDGE_HIT )
  93.  
  94. typedef struct {
  95.     short        tot_edges ;
  96.     unsigned short    gc_flags ;
  97.     GridRec        *gr ;
  98. } GridCell, *pGridCell;
  99.  
  100. typedef struct {
  101.     int        xres, yres ;    /* grid size */
  102.     int        tot_cells ;    /* xres * yres */
  103.     double    minx, maxx, miny, maxy ;    /* bounding box */
  104.     double    xdelta, ydelta ;
  105.     double    inv_xdelta, inv_ydelta ;
  106.     double    *glx, *gly ;
  107.     GridCell    *gc ;
  108. } GridSet, *pGridSet ;
  109.  
  110.  
  111. #ifdef    CONVEX
  112. /* =========== Inclusion stuff ============================================ */
  113. typedef struct {
  114.     double    dot ;        /* angle to beginning of edge */
  115.     double    ex, ey, ec ;    /* edge equation */
  116. } InclusionSet, *pInclusionSet ;
  117.  
  118. typedef struct {
  119.     int            flip_edge ; /* clockwise/counterclockwise */
  120.     int            hi_start ;    /* hi start for binary search: numverts-1 */
  121.     double        ax, ay ;    /* anchor edge vector */
  122.     double        qx, qy ;    /* anchor point */
  123.     pInclusionSet    pis ;
  124. } InclusionAnchor, *pInclusionAnchor ;
  125. #endif    /* end CONVEX */
  126.  
  127. /* =========== Half-Plane stuff =========================================== */
  128.  
  129. typedef struct {
  130.     double    vx, vy, c ;    /* edge equation  vx*X + vy*Y + c = 0 */
  131. #ifdef CONVEX
  132. #ifdef HYBRID
  133.     int        ext_flag ;    /* TRUE == exterior edge of polygon */
  134. #endif
  135. #endif
  136. } PlaneSet, *pPlaneSet ;
  137.  
  138.  
  139. #ifdef    CONVEX
  140. #ifdef    SORT
  141. /* Size sorting structure for half-planes */
  142. typedef struct {
  143.     double    size ;
  144.     pPlaneSet    pps ;
  145. } SizePlanePair, *pSizePlanePair ;
  146. #endif
  147. #endif
  148.  
  149.  
  150. /* =========== Spackman (precomputed barycentric) stuff =================== */
  151. typedef struct {
  152.     double    u1p, u2, v1p, v2, inv_u1, inv_u2, inv_v1 ;
  153.     int        u1_nonzero ;
  154. } SpackmanSet, *pSpackmanSet ;
  155.  
  156.  
  157.  
  158. /* =========== Trapezoid stuff ============================================ */
  159. /* how many bins shall we put the edges into? */
  160. #define TOT_BINS    1000    /* absolutely the maximum number of bins */
  161.  
  162. /* add a little to the limits of the polygon bounding box to avoid precision
  163.  * problems.
  164.  */
  165. #define EPSILON        0.00001
  166.  
  167. /* The following structure is associated with a polygon */
  168. typedef struct {
  169.     int        id ;        /* vertex number of edge */
  170.     int        full_cross ;    /* 1 if extends from top to bottom */
  171.     double    minx, maxx ;    /* X bounds for bin */
  172. } Edge, *pEdge ;
  173.  
  174. typedef struct {
  175.     pEdge    *edge_set ;
  176.     double    minx, maxx ;    /* min and max for all edges in bin */
  177.     int        count ;
  178. } Trapezoid, *pTrapezoid ;
  179.  
  180. typedef struct {
  181.     int        bins ;
  182.     double    minx, maxx ;    /* bounding box for polygon */
  183.     double    miny, maxy ;
  184.     double    ydelta ;    /* (maxy - miny)/bins */
  185.     double    inv_ydelta ;
  186.     Trapezoid    *trapz ;
  187. } TrapezoidSet, *pTrapezoidSet ;
  188.  
  189.  
  190. #ifdef    CONVEX
  191. pPlaneSet    ExteriorSetup() ;
  192. void    ExteriorCleanup() ;
  193.  
  194. pInclusionAnchor    InclusionSetup() ;
  195. void    InclusionCleanup() ;
  196.  
  197. #ifdef    SORT
  198. int    CompareSizePlanePairs() ;
  199. #endif
  200. #endif
  201.  
  202. pPlaneSet    PlaneSetup() ;
  203. void    PlaneCleanup() ;
  204.  
  205. pSpackmanSet    SpackmanSetup() ;
  206. void    SpackmanCleanup() ;
  207.  
  208. void    TrapezoidCleanup() ;
  209. void    TrapBound() ;
  210. int    CompareEdges() ;
  211. void    TrapezoidSetup() ;
  212.  
  213. void    GridSetup() ;
  214. void    GridCleanup() ;
  215.